/*
题目链接：https://leetcode.cn/problems/kth-missing-positive-number/description/
1539. 第k个缺失的正整数-简单
完成日期：2024/9/27
二分搜索
*/
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if(arr[0]>k){
            return k;
        }
        int n=arr.size();
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(mid<n){
                int m=arr[mid];
                if(m-mid-1>=k){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }else{
                int m=INT_MAX;
                if(m-mid-1>=k){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
        }
        int ans=k-(arr[l - 1] - (l - 1) - 1) + arr[l - 1];
        return ans;
    }   
};